\section{Scheduling with and without Priority}
\vspace{-0.5em}
In the framework some simple scheduling algorithms work together to form a complex one, such as DSWC includes LST and EDF. So this chapter introduces these simple scheduling algorithms which are used in the project. These scheduling algorithms are the priority-based scheduling, which means a method where the priority of the application determines whether it runs\cite{scheduling}. After the tasks are ready to be executed, the processor only carries out the task with the highest priority. The priority-based scheduling includes two different kinds of scheduling: fixed-priority scheduling and dynamic-priority scheduling. The following content is about these two different scheduling techniques.
\vspace{-0.5em}
\subsection{Non-Preemptive Scheduling}
\vspace{-0.5em}
Before the detailed explanation of the scheduling, one property of all scheduling in the thesis, "non-preemptive" is firstly explained.

From the simple example in Table \ref{tab:One example of scheduling}, there are two tasks which will be executed by only one processor. The table includes some parameters of two tasks. The Next is how the tasks run in the figure \ref{fig:Preemptive}. At instant of time 0, task A starts to run and ends at instant of time 5. At that time, task B can start to run and it has a higher priority than task A. As a result, at instant of time 5, task B starts to run and task A stops, this is called "preemptive". That means, the task with higher priority is able to interrupt the run of the task with lower priority. After the task B is terminated, task A is able to continue to run.

\begin{table}[h]
\begin{center}
\begin{tabular}[t]{l|c|c|c} % l and c stand for column
\hline  % draw a line of table, and between hline is row
Task & Start & Execution Time & Priority\\
\hline
a & 0 & 10 & Low\\
b & 5 & 10 & High \\
\hline
\end{tabular}
\end{center}
\caption{One example of scheduling}
\label{tab:One example of scheduling}
\end{table}

\begin{figure}[htb!]
\centering
\includegraphics[width=10cm]{Chapter2/non-preemptive1.eps}
\caption{Scheduling result following to the preemptive rule}
\label{fig:Preemptive}
\end{figure}

Figure \ref{fig:Non-Preemptive} shows the opposite situation. At instant of time 5, task B can not interrupt the task A, which is called "non-preemptive". That means, once a task starts to run, it can not be interrupted. If a task is executed, it possesses the highest priority and other tasks must wait.

\begin{figure}[htb!]
\centering
\includegraphics[width=10cm]{Chapter2/non-preemptive2.eps}
\caption{Scheduling result following to the non-preemptive rule}
\label{fig:Non-Preemptive}
\end{figure}

The framework focuses on hardware level where preemption costs are avoided. Preemption occurs usually in higher layers such as in operation systems. So all scheduling techniques in the thesis follow the non-preemptive property.
\vspace{-0.5em}
\subsection{Fixed-Priority Scheduling}
\vspace{-0.5em}
Fixed-priority scheduling means that, the priority of tasks or threads does not change with the time in the priority-based scheduling. So once the priority is determined, it can not be modified.
\vspace{-0.5em}
\subsubsection{Rate Monotonic Scheduling (RMS)}
\vspace{-0.5em}
Rate Monotonic Scheduling, short for RMS, is one of fixed-priority scheduling. "RMS has emerged in the context of task scheduling, where a finite number of periodic tasks share a processor"~\cite{rms}. According to the period of the task, RMS determines the priority of the task. The shorter period the task has, the higher priority it has. The following example explains how the RMS works.

Table \ref{tab:One example of RMS} indicates the periods of three different tasks according to the rule of RMS. They determine the priority of tasks. Because three tasks have the same start time, the priority of tasks determine which task runs first at instant of time 0. Task A has the shortest period, so it owns the highest priority and starts first, which is shown in Figure \ref{fig:RMS}. After the execution time 10 of task A, task C has the higher priority than task B, so task C starts to run at instant of time 10. In the end, task B can be executed. The following execution process of tasks in Figure \ref{fig:RMS} follows the same rule.

\begin{table}[h]
\begin{center}
\begin{tabular}[t]{l|c|c|c|c} % l and c stand for column
\hline  % draw a line of table, and between hline is row
Task & Period & Start & Execution Time & Priority\\
\hline
A & 20 & 0 & 10 & High\\
B & 50 & 0 & 10 & Low\\
C & 30 & 0 & 5  & Medium\\
\hline
\end{tabular}
\end{center}
\caption{One example of RMS}
\label{tab:One example of RMS}
\end{table}

\begin{figure}[htb!]
\centering
\includegraphics[width=10cm]{Chapter2/RMS.eps}
\caption{Scheduling result via RMS}
\label{fig:RMS}
\end{figure}

\vspace{-0.5em}
\subsubsection{Deadline Monotonic Scheduling (DMS)}
\vspace{-0.5em}
The other fixed-priority scheduling is Deadline Monotonic Scheduling (DMS). DMS is similar to RMS, and determines the priority of the task according to the deadline. The task with the shorter deadline is assigned the higher priority.

Table \ref{tab:OneExampleofDMS} describes a simple situation including two executing tasks and Figure \ref{fig:DMS} indicates the execution process of these two tasks according to DMS. Because the deadline of task B is smaller than task A, it has higher priority and runs first.

\begin{table}[h]
\begin{center}
\begin{tabular}[t]{l|c|c|c|c} % l and c stand for column
\hline  % draw a line of table, and between hline is row
Task & Deadline & Start & Execution Time & Priority\\
\hline
A & 20 & 0 & 10 & Low\\
B & 10 & 0 & 10 & High\\
\hline
\end{tabular}
\end{center}
\caption{One example of DMS}
\label{tab:OneExampleofDMS}
\end{table}

\begin{figure}[htb!]
\centering
\includegraphics[width=10cm]{Chapter2/DMS.eps}
\caption{Scheduling result via DMS}
\label{fig:DMS}
\end{figure}

\vspace{-0.5em}
\subsection{Dynamic-Priority Scheduling}
\vspace{-0.5em}
Dynamic-priority scheduling is opposite to the fixed-priority scheduling and the priority of the tasks changes with time. The priority is calculated during the execution process, so the algorithm is able to adjust the priority of tasks to adapt to the changing process of the system. In the project, two different kinds of dynamic-priority scheduling are used, Earliest Deadline First (EDF) and Least Slack Time First (LST).
\vspace{-0.5em}
\subsubsection{Earliest Deadline First (EDF)}
\vspace{-0.5em}
Earliest Deadline First, short for EDF, is the scheduling based on the deadline of tasks. The priority of the task is determined by the distance to the deadline. The task which is closer to the deadline has higher priority. When two tasks have the same absolute deadline, the task to run first is randomly chosen. The following is a simple EDF example.

\begin{table}[h]
\begin{center}
\begin{tabular}[t]{l|c|c|c|c|c} % l and c stand for column
\hline  % draw a line of table, and between hline is row
Task & Start & Deadline & Execution time & Deadline-Start & Priority\\
\hline
a & 0 & 20 & 10 & 20 & High\\
b & 0 & 30 & 10 & 30 & Low\\
\hline
\end{tabular}
\end{center}
\caption{One example of EDF}
\label{tab:One example of EDF}
\end{table}

\begin{figure}[htb!]
\centering
\includegraphics[width=10cm]{Chapter2/EDF1.eps}
\caption{Scheduling result via EDF}
\label{fig:EDF}
\end{figure}

Table \ref{tab:One example of EDF} shows the process how to calculate the priority of task A and B at instant of time 0. Task A has a higher priority than task B, so in Figure \ref{fig:EDF} task A starts to run first. Only after the execution of task A, task B is allowed to be executed.

The advantage of EDF is to fully utilize the processor and reduce idle times~\cite{EDF}. But EDF also has some disadvantages, like less control and less predictability~\cite{EDF}. "Less control" means, nothing is able to reduce the response time of tasks and influence the execution process~\cite{EDF}. The following specific example explains what is "less predictability".

During the overload condition, tasks following the EDF scheduling will miss the deadline in the domino effect. Table \ref{tab:Domino effect} shows an example during the overload condition. Figure \ref{fig:Domino effect} indicates how the tasks miss the deadline: task A has the highest priority at instant of time 0 and it runs first. After task A is terminated, task  b has higher priority than task C, so task B starts to be executed at instant of time 3. But a problem occurs, the deadline of task B is 5, which means, it only has 2 time units to run, but its execution time is 3, so task B has not enough time to finish its job. As a result, task B misses the deadline at instant of time 5. At that time task C starts to run and it has the same problem with task B, so task C also misses its deadline at instant of time 6.

\begin{table}[h]
\begin{center}
\begin{tabular}[t]{l|c|c|c|c|c} % l and c stand for column
\hline  % draw a line of table, and between hline is row
Task & Start & Deadline & Execution time & Priority(0) & Priority(3)\\
\hline
A & 0 & 4 & 3 & High & \\
B & 0 & 5 & 3 & Medium & High\\
C & 0 & 6 & 3 & Low & Low\\
\hline
\end{tabular}
\end{center}
\caption{Example of domino effect}
\label{tab:Domino effect}
\end{table}

\begin{figure}[htb!]
\centering
\includegraphics[width=10cm]{Chapter2/DominoEffect.eps}
\caption{Domino effect}
\label{fig:Domino effect}
\end{figure}

In the EDF scheduling, the overload condition leads to the the domino effect of missing deadline. The question appears how to resolve that problem. Next is presented the improvement algorithm of EDF scheduling, Least Slack Time First (LST).
\vspace{-0.5em}
\subsubsection{Least Slack Time First (LST)}
\vspace{-0.5em}
Least Slack Time First, short for LST, determines the priority of tasks based on the slack time. Slack time is the amount of time left after the task is ready to run. This scheduling algorithm assigns the highest priority to the task which has smallest slack time. Slack time is defined in Equation \ref{slacktime1},
\begin{equation}
s=d-t_{c}-t_{e}
\label{slacktime1}
\end{equation}
where $s$ is the slack time, $d$ is the deadline of task, $t_{c}$ is the current time and $t_{e}$ is the execution time of task. If $s$ is less than zero, the task will miss the deadline so the execution of the task should be canceled.

As mentioned in the last section, EDF scheduling has a domino effect of missing deadline during the overload condition. With the help of the slack time, LST is able to resolve that problem to a certain extent.

Table \ref{tab:LST} shows the same example as in the last section. The only difference is the calculation of the slack time at instant of time 0 and 3. From Table \ref{tab:LST}, task A has the smallest slack time at instant of time 0. So following the rule of LST, it has the highest priority and runs first which is shown in Figure \ref{fig:LST}. The accomplishment of task A is at instant of time 3. From the last column of Table \ref{tab:LST}, the slack of task B is smaller than zero, which means, even if task B starts to run at instant of time 3, it will miss its deadline. So task B is killed. The last one, task C, has zero slack time which predicates that, if task C starts at instant of time 3, it will be terminated before its deadline. In the end, task C runs at instant of time 3 and it finishes at instant of time 6.

\begin{table}[h]
\begin{center}
\begin{tabular}[t]{l|c|c|c|c|c} % l and c stand for column
\hline  % draw a line of table, and between hline is row
Task & Start & Deadline & Execution time & Slack(0) & Slack(3)\\
\hline
A & 0 & 4 & 3 & 1 & \\
B & 0 & 5 & 3 & 2 & $<0$\\
C & 0 & 6 & 3 & 3 & 0\\
\hline
\end{tabular}
\end{center}
\caption{One example of LST}
\label{tab:LST}
\end{table}

\begin{figure}[htb!]
\centering
\includegraphics[width=10cm]{Chapter2/LST.eps}
\caption{Scheduling result via LST}
\label{fig:LST}
\end{figure}

In the EDF scheduling, there are two tasks missing the deadline among all three tasks, while the LST scheduling reduces the number from two to one. In the same example, the different results appear. From this fact it can be concluded, LST is able to reduce the domino effect of missing deadline during the overload condition.
\vspace{-0.5em}
\subsection{ASAP and ALAP Scheduling}
\vspace{-0.5em}
Except the priority-based scheduling, the framework includes ASAP/ALAP scheduling which are shorted for "as soon/late as possible". ASAP/ALAP are able to achieve the simple type of scheduling. Figure \ref{fig:network5nodes} shows a network with five nodes. The network is scheduled via ASAP/ALAP on condition that the number of resources required is infinite.

\begin{figure}[htb!]
\centering
\includegraphics[width=7cm]{Chapter2/network.eps}
\caption{network}
\label{fig:network5nodes}
\end{figure}


\begin{figure}[!hbp]
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=6.5cm]{Chapter2/ASAP.eps}
\caption{Longest path via ASAP}
\label{fig:ASAP}
\end{minipage}
\hspace{0.25cm}
\begin{minipage}[b]{0.5\linewidth}
\centering
\includegraphics[width=6.5cm]{Chapter2/ALAP.eps}
\caption{Longest path via ALAP}
\label{fig:ALAP}
\end{minipage}
\end{figure}

The ASAP scheduling starts each node in the network as soon as its predecessors have terminated, shown in Figure \ref{fig:ASAP}. This scheduling is equal to finding the longest path between each node and the source node~\cite{AsapAlap}. Opposed to ASAP algorithm, the ALAP algorithm schedules each node at the latest opportunity. The ALAP scheduling seeks the longest path between each node and the end sink node, as shown in Figure \ref{fig:ALAP}.




